﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SearchCompare
{
    /// <summary>
    /// Contains methods for building a and using binary search trees
    /// </summary>
    public static unsafe class TreeUtil
    {
        //used to keep track of comparisons when searching for a node in a tree
        private static int _comparisons;

        /// <summary>
        /// Adds a node to an AVL balanced tree, rebalances the tree after the add
        /// </summary>
        /// <param name="node"></param>
        /// <param name="root"></param>
        /// <returns></returns>
        public static bool AVLAdd(Node* node, ref Node* root)
        {
            //See http://www.cse.yorku.ca/course_archive/2008-09/F/2011/slides/22-AVLtrees.pdf
            //To AVL add we need to add the node,adjust the heights, then rebalance if needed

            //Empty tree? New node is now root
            if (root == null)
            {
                root = node;
                return true;
            }

            //else insert as normal into a bst
            else
            {
                bool addsuccess = false;
                if (root->_value > node->_value)
                    addsuccess = AVLAdd(node, ref root->_left);
                else if(root->_value < node->_value)
                    addsuccess = AVLAdd(node, ref root->_right);

                if (addsuccess)
                {
                    Rebalance(ref root);
                    //and recalculate the height
                    AdjustHeight(root);
                }

                return addsuccess;
            }

        }

        /// <summary>
        /// Frees the memory held by each node in the tree
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static void FreeTree(Node* root)
        {
            if (root == null)
                return;
            else
            {
                FreeTree(root->_left);
                FreeTree(root->_right);
                System.Runtime.InteropServices.Marshal.FreeHGlobal((IntPtr)root);
                root->_height = 5;
            }
        }

        /// <summary>
        /// Recursively adds a node to a tree. Returns true if the add was successful, false if the value is already in the tree.
        /// </summary>
        /// <param name="node"></param>
        /// <param name="tree"></param>
        public static bool Add(Node* node, ref Node* root)
        {
            //if you have reached the end of the tree then put the node here
            if (root == null)
            {
                root = node;
                return true;
            }
            //else if node is less than current
            else if (node->_value < root->_value)
            {
                //Add to the left child
                return Add(node, ref root->_left);
            }
            //else call Add on right child
            else if (node->_value > root->_value)
            {
                return Add(node, ref root->_right);
            }

            //if execution makes it here then the value is already present in the tree
            return false;
        }

        /// <summary>
        /// Prints a tree to the console
        /// </summary>
        /// <param name="root"></param>
        public static void PrintTree(Node* root)
        {
            if (root == null)
            {
                return;
            }
            else
            {
                //in order traversal
                PrintTree(root->_left);
                Console.WriteLine("Node: {0}", root->_value);
                PrintTree(root->_right);
            }
        }
        
        /// <summary>
        /// Counts the number of nodes in a tree
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static int Count(Node* root)
        {
            if (root == null)
                return 0;
            else
            {
                return 1 + Count(root->_right) + Count(root->_left);
            }
        }

        /// <summary>
        /// Calculates and returnes the height of a given node/tree
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static int AdjustHeight(Node* root)
        {
            //if root is null then height is 0 by definition
            if (root == null)
                return 0;
            //if root is a leaf then height is 1 by definition
            else if (root->_left == null && root->_right == null)
                root->_height = 1;
            //if a single child is null then height is height of non-null child + 1
            else if (root->_left == null)
                root->_height = root->_right->_height + 1;
            else if (root->_right == null)
                root->_height = root->_left->_height + 1;
            //if both children are non-null then height is max of height of children + 1
            else
                root->_height = 1 + Math.Max(root->_left->_height, root->_right->_height);

            return root->_height;
        }

        /// <summary>
        /// Adjusts the height of every node in the tree
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static int AdjustHeightRecurse(Node* root)
        {
            if (root == null) return 0;
            
            if (Math.Abs(GetHeight(root->_left) - GetHeight(root->_right)) > 1)
                Console.WriteLine("Shit is fucked up. Right: {0}\tLeft{1}", GetHeight(root->_right), GetHeight(root->_left));
        
            return root->_height = Math.Max(AdjustHeightRecurse(root->_left), AdjustHeightRecurse(root->_right)) + 1;
        }

        /// <summary>
        /// returns the height of the node
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public static int GetHeight(Node* node)
        {
            if (node == null)
                return 0;
            else return node->_height;
        }

        /// <summary>
        /// Rebalances a binary search tree designated by root by one shift left or right or a double shift (left-right or right-left).
        /// </summary>
        /// <param name="root"></param>
        public static void Rebalance(ref Node* root)
        {
            
            if (root == null)
                return;

            else if (root->_right == null && root->_left == null)
                return;

            else
            {
                //for left and left-right rotations, heightLL is height(leftchild->leftchild) and so on
                int heightLL, heightLR, heightR = GetHeight(root->_right);

                //for right and right-left rotations, same convention as above
                int heightRR, heightRL, heightL = GetHeight(root->_left);

                if (heightR == 0)
                {
                    heightRR = 0;
                    heightRL = 0;
                }
                else
                {
                    heightRR = GetHeight(root->_right->_right);
                    heightRL = GetHeight(root->_right->_left);
                }
                if (heightL == 0)
                {
                    heightLL = 0;
                    heightLR = 0;
                }
                else
                {
                    heightLL = GetHeight(root->_left->_left);
                    heightLR = GetHeight(root->_left->_right);
                }

                if (heightLL >= heightLR && heightLR >= heightR)
                    root = RotateRight(root);

                else if (heightLR >= heightLL && heightLL >= heightR)
                    root = RotateLR(root);

                else if (heightRR >= heightRL && heightRL >= heightL)
                    root = RotateLeft(root);

                else if (heightRL >= heightRR && heightRR >= heightL)
                    root = RotateRL(root);
            }
            //else tree is balanced, do nothing
        }

        /// <summary>
        /// Used to rebalance the tree to the right
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        private static Node* RotateRight(Node* root)
        {
            Node* result = root->_left;
            root->_left = result->_right;
            result->_right = root;
            AdjustHeight(root);
            AdjustHeight(root->_left);
            AdjustHeight(result);
            return result;
        }

        /// <summary>
        /// Rebalances the tree one shift to the left
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        private static Node* RotateLeft(Node* root)
        {
            Node* result = root->_right;
            root->_right = result->_left;
            result->_left = root;
            AdjustHeight(root);
            AdjustHeight(root->_right);
            AdjustHeight(result);
            return result;

        }

        /// <summary>
        /// Performs a double rotation, right on a child the left on the root
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static Node* RotateRL(Node* root)
        {
            //rotate the right child right
            root->_right = RotateRight(root->_right);

            //then rotate the root left
            Node* result = RotateLeft(root);

            return result;
        }
        
        /// <summary>
        /// Performs a double rotation, left on the left child then right on the root
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static Node* RotateLR(Node* root)
        {
            //Rotate the left child left
            root->_left = RotateLeft(root->_left);
            
            //then rotate the root right
            Node* result = RotateRight(root);

            return result;
        }

        /// <summary>
        /// Returns the number of comparisons needed to find a node in a tree
        /// </summary>
        /// <param name="searchValue"></param>
        /// <param name="root"></param>
        /// <returns></returns>
        public static int MeasureComparisons(ushort searchValue, Node* root)
        {
            //initialize the comparison count
            _comparisons = 0;
            //search for the node
            FindNode(searchValue, root);
            //return the number of comparisons
            return _comparisons;
        }
        
        /// <summary>
        /// Finds a a value in a binary search tree. Returns null if the value does not exist in the tree
        /// </summary>
        /// <param name="searchValue"></param>
        /// <param name="root"></param>
        /// <returns></returns>
        public static Node* FindNode(ushort searchValue, Node* root)
        {
            //each time this is called increment _comparisons to keep track of the number of comparisons required
            //to find the node in a tree
            _comparisons++;

            //if you have reached the end of the tree then the value does not exist in the tree. Return null
            if (root == null)
                return null;

            //if the current node contains the value you are looking for then return it
            else if (root->_value == searchValue)
                return root;

            //if node is less than current searh the left child
            else if (searchValue < root->_value)
                return FindNode(searchValue, root->_left);
            
            //else search the right child
            else
                return FindNode(searchValue, root->_right);
        }
    }
}
